package first.niuke.midding;

import java.util.ArrayList;

/**
 * @ClassName first.niuke.test4
 * @description:
 * @author: 荣燊
 * @create: 2021-04-06 16:58
 **/
public class NC119 {
    // 最小的K个数

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> arrays = new ArrayList<>();

        if (k == 0) {
            return arrays;
        }

        int start = 0;
        int end = input.length-1;
        int index = position(input, start, end);
        while (index != k-1) {
            if (index > k-1) {
                end = index - 1;
                index = position(input, start, end);
            } else {
                start = index + 1;
                index = position(input, start, end);
            }
        }
        for (int i=0; i<k; i++) {
            arrays.add(input[i]);
        }
        return arrays;
    }

    public int position(int[] a, int left, int right) {
        int temp = a[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && a[j] >= temp) {
                j--;
            }
            swap(a, i, j);
            while (i < j && a[i] <= temp) {
                i++;
            }
            swap(a, i, j);
        }
        return i;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}
